#include <stdio.h>
#define swap(a,b) {a=a+b;b=a-b;a=a-b;}
	
// 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

// 基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
// 			  待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
void shell_sort(int arr[], int n)
{
	int i, j, gap, temp;
	for (gap = n/2; gap > 0; gap /= 2) {
		for (i = gap; i < n; i++) {	
			temp = arr[i];
			j = i - gap;
			while (j >= 0 && temp < arr[j]) {
				arr[j+gap] = arr[j];
				j -= gap;
			}
			arr[j+gap] = temp;
		}
	}
}
	
void main()
{
	int i,a[]={13,50,27,-1,70,10,33,82,100,29,5,14,33,50};
	int len = sizeof(a)/sizeof(a[0]);
	shell_sort(a,len);
	for(i=0; i<len; i++)
		printf("%d ", a[i]);
}